#include <stdio.h>
#include <string.h>

#define MAX 32
#define DOUMAX 64

//打印位置信息
void ptstk(int* stk, int top)
{
	int i;
	for (i = 0; i < top; i++) {
		printf("line%d, list%d\n", i+1, stk[i]+1);
	}
	printf("\n");
}
void mirrorpt(int* stk, int top)
{
	int i;
	for (i = 0; i < top; i++) {
		printf("line%d, list%d\n", i+1, top-stk[i]-1);
	}
	printf("\n");
}

//求出解
int getAns(int n)
{
	int sits[MAX][MAX];
	int block = n * n * sizeof(int);
	memset(sits, 0, block);
	int righta[DOUMAX] = {0};
	int lefta[DOUMAX] = {0};
	int stk[MAX] = {0};
	int ckline[MAX] = {0};
	int top = 0;
	int ans = 0;
	int hAns = n % 2;
	int j, k, l;
	for (j = 0, k = 0; ;) {
		while (k < n) {
			l = n - j;
			if (ckline[k] || lefta[j + k] || righta[k + l]) {
				k++;
				continue;
			} else {
				sits[j][k] = 1;
				stk[top++] = k;
				lefta[j + k] = 1;
				righta[k + l] = 1;
				ckline[k] = 1;
				break;
			}
		};
		if (k == n) {
			if (top > 0)
			{
				k = stk[--top];
				sits[--j][k] = 0;
				lefta[j + k] = 0;
				righta[k + n - j] = 0;
				ckline[k] = 0;
				k++;
				continue;
			} else {
				break;
			}

		} else if (j == n-1){
			if (stk[0]+1 > n/2) {
				if (hAns) {
					if (hAns == 1) {
						hAns = ans;
						ans = 0;
					}
					if (stk[0] +1 > (n + 1)/2){
						break;
					}
				} else {
					hAns =ans;
					ans = 0;
					break;
				}
			}

			++ans;
//		ptstk(stk, top);
//		if (hAns <= 1) {
//			mirrorpt(stk, top);
//		}
			k = stk[--top];
			lefta[j+ k] = 0;
			righta[k + l] = 0;
			sits[j--][k] = 0;
			ckline[k] = 0;
			k = stk[--top];
			lefta[j + k] = 0;
			righta[k + n - j] = 0;
			sits[j][k] = 0;
			ckline[k] = 0;
			k++;
			continue;
		}
		j++;
		k = 0;
	}

	return ans + hAns * 2;
}

int main(int argc, char* argv[])
{
	int n = 0;

	printf("input the number of quene:");
	scanf("%d", &n);

	if (n > MAX || n < 0)
		n = 8;

	printf("while n = %d, answer = %d", n, getAns(n));

	return 0;
}
